#include <cstdio>


/**
 * 链式前向星
 * 
 * */
int main() {
    // 点的最大数量
    const int MAXN = 11;
    // 边的最大数量
	// 只有链式前向星方式建图需要这个数量
	// 注意如果无向图的最大数量是m条边，数量要准备m*2
	// 因为一条无向边要加两条有向边
    const int MAXM = 21;
    // 点的数量
    int nodes = 5;

    // 索引是点，值是点对应的第一条边
    int head[MAXN]{};
    // 索引是边，值是下一条边
    int next[MAXM]{};
    // 索引是边，值是边去往的点
    int to[MAXM]{};

    // 权重数组
    int weight[MAXM]{};

    // 当前是第几条边
    int cnt = 1;

    int edges[6][3] = {
        // 1指向2,权重为3
        {1, 2, 3},
        // 2指向1,权重为3
        {2, 1, 3},
        // 2指向3,权重为5
        {2, 3, 5},
        // 3指向5,权重为1
        {3, 5, 1},
        // 4指向5,权重为8
        {4, 5, 8},
        // 5指向1,权重为6
        {5, 1, 6}
    };

    for (const int* edge : edges) {
        // from点
        int f = edge[0];
        // to点
        int t = edge[1];
        // 权重
        int w = edge[2];

        next[cnt] = head[f];
        head[f] = cnt;
        to[cnt] = t;
        weight[cnt] = w;

        cnt++;
    }

    printf("链式前向星构建有向带权图：\n");
    for (int node = 1; node <= nodes; node++) {
        printf("%d -> ", node);
        for (int edge = head[node]; edge > 0;) {
            printf("%d(%d) ", to[edge], weight[edge]);
            edge = next[edge];
        }
        // 打印空格
        printf("\n");
    }

    return 0;
}